#include<cstdio>
#include<cstring>
#include<deque>
using namespace std;

struct edge{
	int x, y, w, pre;
}e[400010];
int elen = 0, last[10010] = {0};
int n, m, d[10010];
bool v[10010] = {false};

void ins(int x, int y, int w) {
	e[++elen] = edge{x, y, w, last[x]};
	last[x] = elen;
}

void spfa() {
	memset(d, 0x3f, sizeof(d));
	d[1] = 0;
	v[1] = true;
	deque<int> dq;
	dq.push_back(1);
	while(!dq.empty()) {
		int x = dq.front();
		for(int k=last[x]; k; k=e[k].pre) {
			int y = e[k].y;
			if(d[y] > d[x] + e[k].w) {
				d[y] = d[x] + e[k].w;
				if(!v[y]) {
					v[y] = true;
					dq.push_back(y);
				}
			}
		}
		dq.pop_front();
		v[x] = false;
	}
	if(d[n] == d[0])	printf("-1\n");
	else				printf("%d\n", d[n]);
}

int main() {
	scanf("%d%d", &n, &m);
	for(int i=0; i<m; i++) {
		int x, y, w;
		scanf("%d%d%d", &x, &y, &w);
		ins(x, y, w);
		ins(y, x, w);
	}
	spfa();
	return 0;
}